class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = 0
        tmp_str = ''
        for i in range(len(s)):
            if not tmp_str:
                tmp_str += s[i]
                
            else:
                if s[i] in tmp_str:
                    tmp_str = tmp_str[tmp_str.index(s[i]) + 1:] + s[i]
                else:
                    tmp_str += s[i]
            length = max(length, len(tmp_str))
        return length    

    def fill_tie_dict(self, tie_tree, word):
        if not word:
            return
        start = word[0]
        if start in tie_tree:
            self.fill_tie_dict(tie_tree[start], word[1:])
        else:
            tie_tree[start] = {}
            self.fill_tie_dict(tie_tree[start], word[1:])

    def walk_dict(self, tie_tree):
        if len(tie_tree) == 1:
            key_one = tie_tree.keys()[0]
            self.layer += key_one
            self.walk_dict(tie_tree[key_one])

    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        tie_tree = {}
        min_len = -1
        for string in strs:
            if min_len == -1:
                min_len = len(string)
            else:
                min_len = min(min_len, len(string))
            self.fill_tie_dict(tie_tree, string)
        self.layer = ''
        self.walk_dict(tie_tree)
        return self.layer[:min_len]

    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        list_s1 = [0] * 26
        for s in s1:
            list_s1[ord(s) - 97] += 1
        print s2
        print s1
        list_s2 = [0] * 26
        start = 0
        match_times = len(s1)
        for i in range(len(s2)):
            s = s2[i]
            pos = ord(s) - 97 
            list_s2[pos] += 1
            match_times -= 1
            if list_s2[pos] > list_s1[pos]:
                for j in range(start, i + 1):
                    match_times += 1
                    s_new = s2[j]
                    pos_new = ord(s_new) - 97 
                    list_s2[pos_new] -= 1
                    if s_new == s:
                        start = j + 1
                        break
            print match_times
            if match_times == 0:
                return True
        return False

    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        ss = s.split(' ')
        ss = filter(lambda s_item: s_item ,ss)
        for i in range(len(ss)):
            ss[i] = ''.join(reversed(ss[i]))

        return ''.join(reversed(' '.join(ss)))

    def ipAddressBc(self, string, index, res_list):
        temp_ss = ''
        if index == 4 and not string:
            self.res_list.append('.'.join(res_list)) 
            return
        for i in range(len(string)):
            temp_ss += string[i]
            int_temp = int(temp_ss)
            if int_temp > 255:
                return
            if len(string) - i > (4 - index) * 3:
                return
            if temp_ss != str(int(temp_ss)):
                return
            res_list.append(temp_ss)
            self.ipAddressBc(string[i+1:], index + 1, res_list)
            res_list.pop()


    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        self.res_list = []
        self.ipAddressBc(s, 0, [])
        return self.res_list

    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_num = 0
        left = []
        for i in xrange(len(height)):
            max_num = max(max_num, height[i])
            left.append(max_num)
        right = []
        max_num = 0
        for i in xrange(len(height) -1, -1, -1):
            max_num = max(max_num, height[i])
            right.append(max_num)
        right.reverse()
        ans = 0
        for i in xrange(len(height)):
            ans += min(left[i], right[i]) - height[i]
        return ans


if __name__ == '__main__':
    ss = '010010'
    s1 = "ab"
    s2 = "eidboaoo"
    ll = ["aa",""]
    nums = [0,1,0,2,1,0,1,3,2,1,2,1]

    aa = Solution()
    print aa.trap(nums)